package com.study.dataStructure.tree.threaded;

/**
 * @author tiny
 * @date 2022/2/9 22:05
 * @Description: 线索化二叉树
 */
public class ThreadedBinaryTree {

    private ThreadedHeroNode threadedHeroNode;

    private ThreadedHeroNode pre = null; //线索化过程中当前结点的前一个结点

    public ThreadedBinaryTree(ThreadedHeroNode threadedHeroNode){
        this.threadedHeroNode = threadedHeroNode;
    }

    public void threadedNodes(){
        threadedNodes(this.threadedHeroNode);
    }

    //中序线索化二叉树
    public void threadedNodes(ThreadedHeroNode root){
        if(root==null) return;

        threadedNodes(root.getLeft());

        //线索化前驱节点
        if(root.getLeft()==null){ //左叶子结点,左指针指向上一个元素
            root.setLeftType(1); //标记是线索化的前一个结点，而不是左子节点
            root.setLeft(pre);
        }
        //线索化后继结点
        if(pre!=null && root.getRight()==null){ //左叶子结点的上一个结点，右指针指向当前结点
            root.setRightType(1);
            pre.setRight(root);
        }

        //pre标记指向下一个待处理的结点；继续下下一个结点线索化
        pre = root;

        threadedNodes(root.getRight());

    }

    //遍历中序线索化二叉树
    public void threadedList(){
        //拿到顶层结点
        ThreadedHeroNode node = this.threadedHeroNode;
        while(node!=null){
            //拿到左叶子结点
            while(node.getLeftType()==0){
                node = node.getLeft();
            }
            System.out.println(node); //输出左叶子结点

            //通过右指针指向的下一个结点不断遍历
            while(node.getRightType()==1){
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();

        }


    }

}
